package com.zp.self.module.level_4_算法练习.算法.排序;

import java.util.Arrays;
import java.util.Random;


/**
 * @author By ZengPeng
 */
public class 猴子排序_量子级别 {
    //测试
    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        int[] ints = {2, 1, 5, 3, 6, 4, 7,8,9,10,11,12};
        System.out.println(Arrays.toString(new 猴子排序_量子级别().monkeySorting(ints)));
        System.out.println("数组长度："+ints.length+" 耗时："+ (System.currentTimeMillis()-l)/1000 +" (s)");
        //数组长度：11 耗时：11 (s)
    }

    /**
    分析：将数组随机打乱，然后再判断是否是递增数列？ 继续随机打乱 ：返回数组
        时间复杂度根据数组长度相关，数组越长，情况越多。
        随机出来的数组情况有：A(n n)  = n * (n-1) *(n-2) * .....* 1
        排列组合问题,理论上时间可以无穷大  -- 故有 【量子猴排】 之称
     **/
    public int[] monkeySorting(int[] nums) {
        while (!isIncreasing(nums))
            shuffle(nums);
        return nums;
    }
   static Random random = new Random();

    public static int[] shuffle(int[] nums) {  //随机打乱数组
        int length  =nums.length;
        for (int i = 0; i < length; i++) {
            int index = random.nextInt(length);
            if(index==i)continue;
            nums[i] = nums[i]^nums[index];
            nums[index] = nums[i]^nums[index];
            nums[i] = nums[i]^nums[index];
        }
        return nums;
    }

    public boolean isIncreasing(int[] nums) {  //随机打乱数组
        int pro=nums[0];
        for (int num : nums) {
           if(num<pro) return false;
           else pro=num;
        }
        return true;
    }
}
